package com.ln.leetcode._1177;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 构建回文串检测
 * <p>
 * 给你一个字符串 s，请你对 s 的子串进行检测。
 * <p>
 * 每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。
 * <p>
 * 如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。
 * <p>
 * 返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。
 * <p>
 * 注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）
 * <p>
 * <p>
 * <p>
 * 示例：
 * <p>
 * 输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
 * 输出：[true,false,false,true,true]
 * 解释：
 * queries[0] : 子串 = "d"，回文。
 * queries[1] : 子串 = "bc"，不是回文。
 * queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
 * queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
 * queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length, queries.length <= 10^5
 * 0 <= queries[i][0] <= queries[i][1] < s.length
 * 0 <= queries[i][2] <= s.length
 * s 中只有小写英文字母
 */
public class Solution {

    @Test
    public void test() {
        System.out.println(canMakePaliQueries("abcda", new int[][]{{3, 3, 0}, {1, 2, 0}, {0, 3, 1}, {0, 3, 2}, {0, 4, 1}}));
        System.out.println(canMakePaliQueries2("abcda", new int[][]{{3, 3, 0}, {1, 2, 0}, {0, 3, 1}, {0, 3, 2}, {0, 4, 1}}));
    }

    /**
     * 官方
     * @param s
     * @param queries
     * @return
     */
    public List<Boolean> canMakePaliQueries2(String s, int[][] queries) {
        int n = s.length();
        int[] count = new int[n + 1];
        for (int i = 0; i < n; i++) {
            count[i + 1] = count[i] ^ (1 << (s.charAt(i) - 'a'));
        }
        List<Boolean> res = new ArrayList<>();
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0], r = queries[i][1], k = queries[i][2];
            int bits = 0, x = count[r + 1] ^ count[l];
            while (x > 0) {
                x &= x - 1;
                bits++;
            }
            res.add(bits <= k * 2 + 1);
        }
        return res;
    }


    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        // 回文判断：
        // 一个字符串能不能是重组成回文，可以通过看其中元素的奇偶次数来判断。如果全是出现了偶数此的字母可以重组成回文，出现一个奇数的字母放在中间，也可以重组成回文
        // 如果一个字符串去修改其中某些字符串来重组成回文，那么修改的数量 k 与 字符串中出现奇数次数总和 n 之前的关系是：n < 2*k+1。意味着k至少是奇数次数的一半才行。
        // 统计字符串上的字符出现的次数：
        // 统计字符串中各个字串出现的次数，可以使用二进制的方式来统计。
        // 将字母 abcd... 按照顺序填充二进制数组中：0000 0000 0101 ... 。每一位上出现1代表字母出现了奇数次
        // 使用二进制 异或的方式(^)，可以达到这样的效果，当字母出现偶数次的时候，该位上的值是`0`，出现奇数次该位上值是`1`
        // 最终我们关注的是 `1` 的次数

        // 解题：
        int length = s.length();
        // count[i+1] 标识了 s从右开始第i个字串中字符出现奇偶次数的情况
        // "abcda" ==> [[0], [1], [11], [111], [1111], [1110]]
        int[] count = new int[length + 1];
        for (int i = 0; i < length; i++) {
            count[i + 1] = count[i] ^ (1 << (s.charAt(i) - 'a'));
        }

        List<Boolean> ans = new ArrayList<>();
        // 循环条件求解
        for (int i = 0; i < queries.length; i++) {
            // 定义出 l，r，k
            int l = queries[i][0];
            int r = queries[i][1];
            int k = queries[i][2];
            // todo ???
            int binaryNum = count[l] ^ count[r + 1];
            int oddCount = 0;
            // todo ???
            while (binaryNum > 0) {
                binaryNum &= binaryNum - 1;
                ++oddCount;
            }
            ans.add(oddCount <= 2 * k + 1);
        }
        return ans;
    }

    @Test
    public void test1() {
        String s = "abcda";
        int length = s.length();
        int[] count = new int[length + 1];
        for (int i = 0; i < length; i++) {
            count[i + 1] = count[i] ^ (1 << (s.charAt(i) - 'a'));
        }
        Arrays.stream(count).forEach(c -> {
            System.out.printf("%d ==> %s \n", c, Integer.toBinaryString(c));
        });

        System.out.println("===================");
        int n1 = 15;
        while (n1 > 0) {
            n1 &= n1 - 1;
            System.out.printf("%d -> %s \n", n1, Integer.toBinaryString(n1));
        }


    }

}
